//
// Description: 743. 网络延迟时间
// Created by Loading on 2021/8/2.
//

#include <bits/stdc++.h>

using namespace std;

int networkDelayTime(vector<vector<int>> &times, int n, int k) {
    /* 求起点到其他所有点的最短距离，取最长则为结果 */
    constexpr int inf = 0x3f3f3f3f;

    // 存储边的起始和结尾，以及权重
    vector<vector<pair<int, int>>> g(n);
    for (auto &v : times) {
        g[v[0] - 1].emplace_back(v[1] - 1, v[2]);
    }

    // 起点 k 到每个点的最短距离
    vector<int> distances(n, inf);
    distances[k - 1] = 0;

    // 优先级队列，<起点到某个节点的距离，节点>，按照距离降序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    q.emplace(0, k - 1);
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        // 这条路径不是最短路径，则这条路径后的路径一定不是最短，无需继续遍历
        if (distances[p.second] < p.first) {
            continue;
        }
        // 遍历这个节点的后续节点
        for (auto[target, dis] : g[p.second]) {
            int dis_cnt = dis + distances[p.second];
            // 发现较短路径
            if (distances[target] > dis_cnt) {
                distances[target] = dis_cnt;
                // 将较短路径加入队列
                q.emplace(dis_cnt, target);
            }
        }
    }

    int res = *max_element(distances.begin(), distances.end());
    return res == inf ? -1 : res;
}

int main() {
    vector<vector<int>> times = {{2, 1, 1},
                                 {2, 3, 1},
                                 {3, 4, 1}};
    int k = 2;
    int n = 4;
    cout << networkDelayTime(times, n, k) << endl;
}